The SLIC and SLICO algorithms

Each pixel in an image contains two types of information: its color, represented by a vector in a three dimensional space such as the RGN or CIELAB color space, and its location, represented by a vector in two dimensional space (its x and y coordinates). Thus the totality of information in a pixel is a vector in a five dimensional space.

The SLIC and SLICO algorithms perform a clustering operation similar to K-means clustering on the collection of pixels as represented in this five-dimensional space.

library(sp)
library(raster)

Step 1.0: Read the sattelite images for the blue, green, red, and near infrared bands as RasterLayer objects.

# step 1.0
# path to images
droneImagesPath <- "MachineLearningClass/DroneImages/"
droneImageName <- "NobalWheat_NUE_7-6-2021_20m_transparent_reflectance"
#print(getwd())
#print(sprintf("%s%s%s", droneImagesPath, droneImageName, "_blue.tif"))
setwd('..')
Warning: The working directory was changed to /Volumes/Data Science 214386/DataScience214386/MTAT.03.227 - Machine Learning/Project/P08 - Differentiation of weeds and crop plants from drone imagery, Computer vision inside a notebook chunk. The working directory will be reset when the chunk is finished running. Use the knitr root.dir option in the setup chunk to change the working directory for notebook chunks.
#print(getwd())
b2 <- raster(sprintf("%s%s%s", droneImagesPath, droneImageName, "_blue.tif")) # Blue
Warning in showSRID(SRS_string, format = "PROJ", multiline = "NO", prefer_proj = prefer_proj) :
  Discarded datum Estonia 1997 in Proj4 definition
b3 <- raster(sprintf("%s%s%s", droneImagesPath, droneImageName, "_green.tif")) # Green
Warning in showSRID(SRS_string, format = "PROJ", multiline = "NO", prefer_proj = prefer_proj) :
  Discarded datum Estonia 1997 in Proj4 definition
b4 <- raster(sprintf("%s%s%s", droneImagesPath, droneImageName, "_red.tif")) # Red
Warning in showSRID(SRS_string, format = "PROJ", multiline = "NO", prefer_proj = prefer_proj) :
  Discarded datum Estonia 1997 in Proj4 definition
b5 <- raster(sprintf("%s%s%s", droneImagesPath, droneImageName, "_nir.tif")) # NIR
Warning in showSRID(SRS_string, format = "PROJ", multiline = "NO", prefer_proj = prefer_proj) :
  Discarded datum Estonia 1997 in Proj4 definition
b2[is.na(b2)] <- 0
b3[is.na(b3)] <- 0
b4[is.na(b4)] <- 0
b5[is.na(b5)] <- 0
#b6 <- raster(sprintf("%s%s%s", droneImagesPath, droneImageName, "_red edge.tif")) # Red Edge

Step 1.1: Create a RasterBrick object.

# step 1.1
full.brick <- brick(b2, b3, b4, b5)
Warning in showSRID(uprojargs, format = "PROJ", multiline = "NO", prefer_proj = prefer_proj) :
  Discarded datum Unknown based on GRS80 ellipsoid in Proj4 definition
names(full.brick) <- c("blue", "green", "red", "IR")
writeRaster(full.brick, filename = "regions/region.grd", bylayer = TRUE, suffix = names(full.brick), overwrite=TRUE)
Warning in showSRID(uprojargs, format = "PROJ", multiline = "NO", prefer_proj = prefer_proj) :
  Discarded datum Unknown based on GRS80 ellipsoid in Proj4 definition
Warning in showSRID(uprojargs, format = "PROJ", multiline = "NO", prefer_proj = prefer_proj) :
  Discarded datum Unknown based on GRS80 ellipsoid in Proj4 definition
Warning in showSRID(uprojargs, format = "PROJ", multiline = "NO", prefer_proj = prefer_proj) :
  Discarded datum Unknown based on GRS80 ellipsoid in Proj4 definition
Warning in showSRID(uprojargs, format = "PROJ", multiline = "NO", prefer_proj = prefer_proj) :
  Discarded datum Unknown based on GRS80 ellipsoid in Proj4 definition

Step 2.1: Read RasterBrick object from disk.

Step 2.2: Plot the region.brick object and wrote it to disk. As a result we get the False color image of the region.

# step 2.1
full.brick <- brick(b2, b3, b4, b5)
Warning in showSRID(uprojargs, format = "PROJ", multiline = "NO", prefer_proj = prefer_proj) :
  Discarded datum Unknown based on GRS80 ellipsoid in Proj4 definition
names(full.brick) <- c("blue", "green", "red", "IR")
writeRaster(full.brick, filename = "regions/region.grd", bylayer = TRUE, suffix = names(full.brick), overwrite=TRUE)
Warning in showSRID(uprojargs, format = "PROJ", multiline = "NO", prefer_proj = prefer_proj) :
  Discarded datum Unknown based on GRS80 ellipsoid in Proj4 definition
Warning in showSRID(uprojargs, format = "PROJ", multiline = "NO", prefer_proj = prefer_proj) :
  Discarded datum Unknown based on GRS80 ellipsoid in Proj4 definition
Warning in showSRID(uprojargs, format = "PROJ", multiline = "NO", prefer_proj = prefer_proj) :
  Discarded datum Unknown based on GRS80 ellipsoid in Proj4 definition
Warning in showSRID(uprojargs, format = "PROJ", multiline = "NO", prefer_proj = prefer_proj) :
  Discarded datum Unknown based on GRS80 ellipsoid in Proj4 definition
b2 <- raster("regions/region_blue.grd")
Warning in showSRID(uprojargs, format = "PROJ", multiline = "NO", prefer_proj = prefer_proj) :
  Discarded datum Unknown based on GRS80 ellipsoid in Proj4 definition
b3 <- raster("regions/region_green.grd")
Warning in showSRID(uprojargs, format = "PROJ", multiline = "NO", prefer_proj = prefer_proj) :
  Discarded datum Unknown based on GRS80 ellipsoid in Proj4 definition
b4 <- raster("regions/region_red.grd")
Warning in showSRID(uprojargs, format = "PROJ", multiline = "NO", prefer_proj = prefer_proj) :
  Discarded datum Unknown based on GRS80 ellipsoid in Proj4 definition
b5 <- raster("regions/region_IR.grd")
Warning in showSRID(uprojargs, format = "PROJ", multiline = "NO", prefer_proj = prefer_proj) :
  Discarded datum Unknown based on GRS80 ellipsoid in Proj4 definition
region.brick <- brick(b2, b3, b4, b5)
Warning in showSRID(uprojargs, format = "PROJ", multiline = "NO", prefer_proj = prefer_proj) :
  Discarded datum Unknown based on GRS80 ellipsoid in Proj4 definition
#print(nrows <- region.brick@nrows)
#print(ncols <- region.brick@ncols)

# step 2.2
# plot the region/brick object and write it to disk
plotRGB(region.brick, r = 4, g = 3, b = 2, stretch = "lin")
# write the image to disk
jpeg("FalseColor.jpg", width = ncols, height = nrows)
plotRGB(region.brick, r = 4, g = 3, b = 2, stretch = "lin")
dev.off()
quartz_off_screen 
                2 

Step 3.1: Use SLIC for False Color image segmentation.

# step 3.1
# use SLIC for image segmentation
library(OpenImageR)
False.Color <- readImage("FalseColor.jpg")
Region.slic = superpixels(input_image = False.Color,
                       method = "slic",  #method = "slico",
                       superpixel = 27,  #superpixel = 200,
                       compactness = 3, 
                       return_slic_data = TRUE,
                       return_labels = TRUE, 
                       write_slic = "", 
                       verbose = FALSE)
Warning in interface_superpixels(input_image, method, superpixel, compactness,  :
  The input data has values between 0.000000 and 1.000000. The image-data will be multiplied by the value: 255!
OpenImageR::imageShow(Region.slic$slic_data) #Fig. 5
plot_slic = OpenImageR::NormalizeObject(Region.slic$slic_data)
plot_slic = grDevices::as.raster(plot_slic)
graphics::plot(plot_slic)

Step 4.1: Computing NDVI and plot NDVI.region. The darkest areas have the highest NDVI.

Step 4.2: Since NDVI is a ratio scale quantity, the theoretically best practice is to plot it using a monochromatic representation in which the brightness of the color (i.e., the color value) represents the value.

Step 4.2.1: Convert the raster data to a matrix that can be imported into our image segmentation machinery. Remember that by default R constructs matrices by columns. The data in Raster* objects such as NDVI.region are stored by rows, so in converting these data to a matrix we must specify byrow=TRUE.

Step 4.2.2: The function imageShow() works with data that are either in the eight bit 0 - 255 range or in the \[0,1\] range (i.e., the range of x such that 0<=x<=1). It does not, however, work with NDVI values if these values are negative. Therefor, we will scale NDVI values to \[0,1\].

# Step 4.1
library(RColorBrewer)
# compute NDVI
NDVI.region <- (b5 - b4) / (b5 + b4)
plot(NDVI.region, col = brewer.pal(9, "Greens"), axes = TRUE, main = "Region NDVI")


# Step 4.2
# Step 4.2.1
NDVI.region[is.na(NDVI.region)] <- 0
NDVI.mat <- matrix(NDVI.region@data@values, nrow = NDVI.region@nrows, ncol = NDVI.region@ncols, byrow = TRUE)
# Step 4.2.2
# Scale the NDVI to [0,1]
m0 <- min(NDVI.mat)
m1 <- max(NDVI.mat)
NDVI.mat1 <- (NDVI.mat - m0) / (m1 - m0)

#OpenImageR::imageShow(NDVI.mat1)  # Fig. 9
plot_slic = OpenImageR::NormalizeObject(NDVI.mat1)
plot_slic = grDevices::as.raster(plot_slic)
graphics::plot(plot_slic)

Step 5.1: We are now ready to carry out the segmentation of the NDVI data. Since the structure of the NDVI image to be analyzed is the same as that of the false color image, we can simply create a copy of this image, fill it with the NDVI data, and run it through the superpixel segmentation function.

# Step 5.1
False.Color <- readImage("FalseColor.jpg")
NDVI.data <- False.Color
NDVI.data[,,1] <- NDVI.mat1
NDVI.data[,,2] <- NDVI.mat1
NDVI.data[,,3] <- NDVI.mat1

NDVI.80 = superpixels(input_image = NDVI.data,
                      method = "slic",  #method = "slico",
                      superpixel = 37,   #superpixel = 200,
                      compactness = 3, 
                      return_slic_data = TRUE,
                      return_labels = TRUE, 
                      write_slic = "",
                      verbose = FALSE)
Warning in interface_superpixels(input_image, method, superpixel, compactness,  :
  The input data has values between 0.000000 and 1.000000. The image-data will be multiplied by the value: 255!
OpenImageR::imageShow(NDVI.80$slic_data)
plot_slic = OpenImageR::NormalizeObject(NDVI.80$slic_data)
plot_slic = grDevices::as.raster(plot_slic)
graphics::plot(plot_slic)

The segmentation process is now can be organized into two steps.

The first step will be to replace each of the superpixels generated by the OpenImageR function superpixel() with one in which each pixel has the same value, corresponding to a measure of central tendency (e.g. mean) of the original superpixel.

Function: Identify a measure of central tendency of each superpixel

# Identify a measure of central tendency of each superpixel
make.segments <- function(x, ftn){
# The argument ftn is any functional measure of central tendency
   z <- x
# For each identified superpixel, compute measure of central tendency
   for (k in unique(as.vector(x$labels))){
# Identify members of the superpixel having the given label
      in.super <- matrix(0, nrow(x$label), ncol(x$label))
      for (i in 1:nrow(x$label))
         for (j in 1:ncol(x$label))
            if (x$label[i,j] == k)
               in.super[i,j] <- 1
#Identify the boundary cells as having all values 0
      on.bound <- matrix(0, nrow(x$label), ncol(x$label))
      for (i in 1:nrow(x$label))
         for (j in 1:ncol(x$label))
            if (in.super[i,j] == 1){
               if (x$slic_data[i,j,1] == 0 & x$slic_data[i,j,2] == 0 
                  & x$slic_data[i,j,3] == 0)
                     on.bound[i,j] <- 1
         }
#Identify the superpixel cells not on the boundary
      sup.data <- matrix(0, nrow(x$label), ncol(x$label))
         for (i in 1:nrow(x$label))
         for (j in 1:ncol(x$label))
            if (in.super[i,j] == 1 & on.bound[i,j] == 0)
               sup.data[i,j] <- 1
# Compute the measure of central tendency of the cells in R, G, B
      for (n in 1:3){
# Create a matrix M of the same size as the matrix of superpixel values
         M <- matrix(0, dim(x$slic_data)[1], dim(x$slic_data)[2]) 
         for (i in 1:nrow(x$label))
            for (j in 1:ncol(x$label))
# Assign to M the values in the superpixel
               if (sup.data[i,j] == 1) M[i,j] <- x$slic_data[i,j,n]
          if (length(M[which(M > 0 & M < 255)]) > 0)
# Compute the measure of central tendency
            ftn.n <- round(ftn(M[which(M > 0 & M < 255)]), 0)
         else
            ftn.n <- 0
         for (i in 1:nrow(x$label))
            for (j in 1:ncol(x$label))
               if (in.super[i,j] == 1) z$slic_data[i,j,n] <- ftn.n
           }
      }
   return(z)
   }
NDVI.means <-  make.segments(NDVI.80, mean)

The second step will be to use the k-means unsupervised clustering procedure to organize the superpixels from step 1 into a set of clusters and give each cluster a value corresponding to a measure of central tendency of the cluster.

The land is ubdivided into five types: 1, 2, 3, 4, 5.

The raster function ratify() is used to assign descriptive factor levels to the clusters.

library(rasterVis)
# Look at the individual values
sort(unique(as.vector(NDVI.means$slic_data[,,1])))
 [1] 127 202 203 205 206 207 212 215 217 228 230 236 238 239 240 241 243 244 246
# Group into five clusters
set.seed(123) 
NDVI.clus <- kmeans(as.vector(NDVI.means$slic_data[,,1]), 5)
vege.class <- matrix(NDVI.clus$cluster, nrow = NDVI.region@nrows,
   ncol = NDVI.region@ncols, byrow = FALSE)
imageShow(vege.class) # Just a check not shown as a figure
plot_slic = OpenImageR::NormalizeObject(vege.class)
plot_slic = grDevices::as.raster(plot_slic)
graphics::plot(plot_slic)

class.ras <- raster(vege.class)
class.ras <- ratify(class.ras)
rat.class <- levels(class.ras)[[1]]
rat.class$landcover <- c("1", "2", "3", "4", "5")
levels(class.ras) <- rat.class
levelplot(class.ras, margin=FALSE, col.regions= c("lightgreen", "black",
  "tan", "darkgreen", "beige"), main = "Land Cover Types") # Fig. 19

plot(class.ras, col = c("lightgreen", "black",
  "tan", "darkgreen", "beige"), main = "Land Cover Types",
   legend = FALSE) # Fig. 19

#legend("right", legend = c("1", "2", "3", "4",
#  "5"), fill = c("darkgreen", "tan", "lightgreen", "green",
#  "black"))
#plot(NDVI.polymns, add = TRUE) 
LS0tCnRpdGxlOiAiUiBOb3RlYm9vayIKb3V0cHV0OiBodG1sX25vdGVib29rCi0tLQoKKipUaGUgU0xJQyBhbmQgU0xJQ08gYWxnb3JpdGhtcyoqCgpFYWNoIHBpeGVsIGluIGFuIGltYWdlIGNvbnRhaW5zIHR3byB0eXBlcyBvZiBpbmZvcm1hdGlvbjogaXRzIGNvbG9yLCByZXByZXNlbnRlZCBieSBhIHZlY3RvciBpbiBhIHRocmVlIGRpbWVuc2lvbmFsIHNwYWNlIHN1Y2ggYXMgdGhlIFJHTiBvciBDSUVMQUIgY29sb3Igc3BhY2UsIGFuZCBpdHMgbG9jYXRpb24sIHJlcHJlc2VudGVkIGJ5IGEgdmVjdG9yIGluIHR3byBkaW1lbnNpb25hbCBzcGFjZSAoaXRzICp4KiBhbmQgKnkqIGNvb3JkaW5hdGVzKS4gVGh1cyB0aGUgdG90YWxpdHkgb2YgaW5mb3JtYXRpb24gaW4gYSBwaXhlbCBpcyBhIHZlY3RvciBpbiBhIGZpdmUgZGltZW5zaW9uYWwgc3BhY2UuCgpUaGUgU0xJQyBhbmQgU0xJQ08gYWxnb3JpdGhtcyBwZXJmb3JtIGEgY2x1c3RlcmluZyBvcGVyYXRpb24gc2ltaWxhciB0byBLLW1lYW5zIGNsdXN0ZXJpbmcgb24gdGhlIGNvbGxlY3Rpb24gb2YgcGl4ZWxzIGFzIHJlcHJlc2VudGVkIGluIHRoaXMgZml2ZS1kaW1lbnNpb25hbCBzcGFjZS4KCmBgYHtyfQpsaWJyYXJ5KHNwKQpsaWJyYXJ5KHJhc3RlcikKYGBgCgoqKlN0ZXAgMS4wOioqIFJlYWQgdGhlIHNhdHRlbGl0ZSBpbWFnZXMgZm9yIHRoZSBibHVlLCBncmVlbiwgcmVkLCBhbmQgbmVhciBpbmZyYXJlZCBiYW5kcyBhcyBSYXN0ZXJMYXllciBvYmplY3RzLgoKYGBge3J9CiMgc3RlcCAxLjAKIyBwYXRoIHRvIGltYWdlcwpkcm9uZUltYWdlc1BhdGggPC0gIk1hY2hpbmVMZWFybmluZ0NsYXNzL0Ryb25lSW1hZ2VzLyIKZHJvbmVJbWFnZU5hbWUgPC0gIk5vYmFsV2hlYXRfTlVFXzctNi0yMDIxXzIwbV90cmFuc3BhcmVudF9yZWZsZWN0YW5jZSIKI3ByaW50KGdldHdkKCkpCiNwcmludChzcHJpbnRmKCIlcyVzJXMiLCBkcm9uZUltYWdlc1BhdGgsIGRyb25lSW1hZ2VOYW1lLCAiX2JsdWUudGlmIikpCnNldHdkKCcuLicpCiNwcmludChnZXR3ZCgpKQpiMiA8LSByYXN0ZXIoc3ByaW50ZigiJXMlcyVzIiwgZHJvbmVJbWFnZXNQYXRoLCBkcm9uZUltYWdlTmFtZSwgIl9ibHVlLnRpZiIpKSAjIEJsdWUKYjMgPC0gcmFzdGVyKHNwcmludGYoIiVzJXMlcyIsIGRyb25lSW1hZ2VzUGF0aCwgZHJvbmVJbWFnZU5hbWUsICJfZ3JlZW4udGlmIikpICMgR3JlZW4KYjQgPC0gcmFzdGVyKHNwcmludGYoIiVzJXMlcyIsIGRyb25lSW1hZ2VzUGF0aCwgZHJvbmVJbWFnZU5hbWUsICJfcmVkLnRpZiIpKSAjIFJlZApiNSA8LSByYXN0ZXIoc3ByaW50ZigiJXMlcyVzIiwgZHJvbmVJbWFnZXNQYXRoLCBkcm9uZUltYWdlTmFtZSwgIl9uaXIudGlmIikpICMgTklSCmIyW2lzLm5hKGIyKV0gPC0gMApiM1tpcy5uYShiMyldIDwtIDAKYjRbaXMubmEoYjQpXSA8LSAwCmI1W2lzLm5hKGI1KV0gPC0gMAojYjYgPC0gcmFzdGVyKHNwcmludGYoIiVzJXMlcyIsIGRyb25lSW1hZ2VzUGF0aCwgZHJvbmVJbWFnZU5hbWUsICJfcmVkIGVkZ2UudGlmIikpICMgUmVkIEVkZ2UKCmBgYAoKKipTdGVwIDEuMToqKiBDcmVhdGUgYSBSYXN0ZXJCcmljayBvYmplY3QuCgpgYGB7cn0KIyBzdGVwIDEuMQpmdWxsLmJyaWNrIDwtIGJyaWNrKGIyLCBiMywgYjQsIGI1KQpuYW1lcyhmdWxsLmJyaWNrKSA8LSBjKCJibHVlIiwgImdyZWVuIiwgInJlZCIsICJJUiIpCndyaXRlUmFzdGVyKGZ1bGwuYnJpY2ssIGZpbGVuYW1lID0gInJlZ2lvbnMvcmVnaW9uLmdyZCIsIGJ5bGF5ZXIgPSBUUlVFLCBzdWZmaXggPSBuYW1lcyhmdWxsLmJyaWNrKSwgb3ZlcndyaXRlPVRSVUUpCmBgYAoKKipTdGVwIDIuMToqKiBSZWFkIFJhc3RlckJyaWNrIG9iamVjdCBmcm9tIGRpc2suCgoqKlN0ZXAgMi4yOioqIFBsb3QgdGhlIHJlZ2lvbi5icmljayBvYmplY3QgYW5kIHdyb3RlIGl0IHRvIGRpc2suIEFzIGEgcmVzdWx0IHdlIGdldCB0aGUgRmFsc2UgY29sb3IgaW1hZ2Ugb2YgdGhlIHJlZ2lvbi4KCmBgYHtyfQojIHN0ZXAgMi4xCmZ1bGwuYnJpY2sgPC0gYnJpY2soYjIsIGIzLCBiNCwgYjUpCm5hbWVzKGZ1bGwuYnJpY2spIDwtIGMoImJsdWUiLCAiZ3JlZW4iLCAicmVkIiwgIklSIikKd3JpdGVSYXN0ZXIoZnVsbC5icmljaywgZmlsZW5hbWUgPSAicmVnaW9ucy9yZWdpb24uZ3JkIiwgYnlsYXllciA9IFRSVUUsIHN1ZmZpeCA9IG5hbWVzKGZ1bGwuYnJpY2spLCBvdmVyd3JpdGU9VFJVRSkKCmIyIDwtIHJhc3RlcigicmVnaW9ucy9yZWdpb25fYmx1ZS5ncmQiKQpiMyA8LSByYXN0ZXIoInJlZ2lvbnMvcmVnaW9uX2dyZWVuLmdyZCIpCmI0IDwtIHJhc3RlcigicmVnaW9ucy9yZWdpb25fcmVkLmdyZCIpCmI1IDwtIHJhc3RlcigicmVnaW9ucy9yZWdpb25fSVIuZ3JkIikKcmVnaW9uLmJyaWNrIDwtIGJyaWNrKGIyLCBiMywgYjQsIGI1KQoKI3ByaW50KG5yb3dzIDwtIHJlZ2lvbi5icmlja0Bucm93cykKI3ByaW50KG5jb2xzIDwtIHJlZ2lvbi5icmlja0BuY29scykKCiMgc3RlcCAyLjIKIyBwbG90IHRoZSByZWdpb24vYnJpY2sgb2JqZWN0IGFuZCB3cml0ZSBpdCB0byBkaXNrCnBsb3RSR0IocmVnaW9uLmJyaWNrLCByID0gNCwgZyA9IDMsIGIgPSAyLCBzdHJldGNoID0gImxpbiIpCiMgd3JpdGUgdGhlIGltYWdlIHRvIGRpc2sKanBlZygiRmFsc2VDb2xvci5qcGciLCB3aWR0aCA9IG5jb2xzLCBoZWlnaHQgPSBucm93cykKcGxvdFJHQihyZWdpb24uYnJpY2ssIHIgPSA0LCBnID0gMywgYiA9IDIsIHN0cmV0Y2ggPSAibGluIikKZGV2Lm9mZigpCgpgYGAKCioqU3RlcCAzLjE6KiogVXNlIFNMSUMgZm9yIEZhbHNlIENvbG9yIGltYWdlIHNlZ21lbnRhdGlvbi4KCmBgYHtyfQojIHN0ZXAgMy4xCiMgdXNlIFNMSUMgZm9yIGltYWdlIHNlZ21lbnRhdGlvbgpsaWJyYXJ5KE9wZW5JbWFnZVIpCkZhbHNlLkNvbG9yIDwtIHJlYWRJbWFnZSgiRmFsc2VDb2xvci5qcGciKQpSZWdpb24uc2xpYyA9IHN1cGVycGl4ZWxzKGlucHV0X2ltYWdlID0gRmFsc2UuQ29sb3IsCiAgICAgICAgICAgICAgICAgICAgICAgbWV0aG9kID0gInNsaWMiLCAgI21ldGhvZCA9ICJzbGljbyIsCiAgICAgICAgICAgICAgICAgICAgICAgc3VwZXJwaXhlbCA9IDI3LCAgI3N1cGVycGl4ZWwgPSAyMDAsCiAgICAgICAgICAgICAgICAgICAgICAgY29tcGFjdG5lc3MgPSAzLCAKICAgICAgICAgICAgICAgICAgICAgICByZXR1cm5fc2xpY19kYXRhID0gVFJVRSwKICAgICAgICAgICAgICAgICAgICAgICByZXR1cm5fbGFiZWxzID0gVFJVRSwgCiAgICAgICAgICAgICAgICAgICAgICAgd3JpdGVfc2xpYyA9ICIiLCAKICAgICAgICAgICAgICAgICAgICAgICB2ZXJib3NlID0gRkFMU0UpCgpPcGVuSW1hZ2VSOjppbWFnZVNob3coUmVnaW9uLnNsaWMkc2xpY19kYXRhKSAjRmlnLiA1CnBsb3Rfc2xpYyA9IE9wZW5JbWFnZVI6Ok5vcm1hbGl6ZU9iamVjdChSZWdpb24uc2xpYyRzbGljX2RhdGEpCnBsb3Rfc2xpYyA9IGdyRGV2aWNlczo6YXMucmFzdGVyKHBsb3Rfc2xpYykKZ3JhcGhpY3M6OnBsb3QocGxvdF9zbGljKQpgYGAKCioqU3RlcCA0LjE6KiogQ29tcHV0aW5nIE5EVkkgYW5kIHBsb3QgTkRWSS5yZWdpb24uIFRoZSBkYXJrZXN0IGFyZWFzIGhhdmUgdGhlIGhpZ2hlc3QgTkRWSS4KCioqU3RlcCA0LjI6KiogU2luY2UgTkRWSSBpcyBhIHJhdGlvIHNjYWxlIHF1YW50aXR5LCB0aGUgdGhlb3JldGljYWxseSBiZXN0IHByYWN0aWNlIGlzIHRvIHBsb3QgaXQgdXNpbmcgYSBtb25vY2hyb21hdGljIHJlcHJlc2VudGF0aW9uIGluIHdoaWNoIHRoZSBicmlnaHRuZXNzIG9mIHRoZSBjb2xvciAoaS5lLiwgdGhlIGNvbG9yIHZhbHVlKSByZXByZXNlbnRzIHRoZSB2YWx1ZS4KCioqU3RlcCA0LjIuMToqKiBDb252ZXJ0IHRoZSByYXN0ZXIgZGF0YSB0byBhIG1hdHJpeCB0aGF0IGNhbiBiZSBpbXBvcnRlZCBpbnRvIG91ciBpbWFnZSBzZWdtZW50YXRpb24gbWFjaGluZXJ5LiBSZW1lbWJlciB0aGF0IGJ5IGRlZmF1bHQgUiBjb25zdHJ1Y3RzIG1hdHJpY2VzIGJ5IGNvbHVtbnMuIFRoZSBkYXRhIGluIFJhc3RlclwqIG9iamVjdHMgc3VjaCBhcyBORFZJLnJlZ2lvbiBhcmUgc3RvcmVkIGJ5IHJvd3MsIHNvIGluIGNvbnZlcnRpbmcgdGhlc2UgZGF0YSB0byBhIG1hdHJpeCB3ZSBtdXN0IHNwZWNpZnkgYnlyb3c9VFJVRS4KCioqU3RlcCA0LjIuMjoqKiBUaGUgZnVuY3Rpb24gaW1hZ2VTaG93KCkgd29ya3Mgd2l0aCBkYXRhIHRoYXQgYXJlIGVpdGhlciBpbiB0aGUgZWlnaHQgYml0IDAgLSAyNTUgcmFuZ2Ugb3IgaW4gdGhlIFxbMCwxXF0gcmFuZ2UgKGkuZS4sIHRoZSByYW5nZSBvZiB4IHN1Y2ggdGhhdCAwXDw9eFw8PTEpLiBJdCBkb2VzIG5vdCwgaG93ZXZlciwgd29yayB3aXRoIE5EVkkgdmFsdWVzIGlmIHRoZXNlIHZhbHVlcyBhcmUgbmVnYXRpdmUuIFRoZXJlZm9yLCB3ZSB3aWxsIHNjYWxlIE5EVkkgdmFsdWVzIHRvIFxbMCwxXF0uCgpgYGB7cn0KIyBTdGVwIDQuMQpsaWJyYXJ5KFJDb2xvckJyZXdlcikKIyBjb21wdXRlIE5EVkkKTkRWSS5yZWdpb24gPC0gKGI1IC0gYjQpIC8gKGI1ICsgYjQpCnBsb3QoTkRWSS5yZWdpb24sIGNvbCA9IGJyZXdlci5wYWwoOSwgIkdyZWVucyIpLCBheGVzID0gVFJVRSwgbWFpbiA9ICJSZWdpb24gTkRWSSIpCgojIFN0ZXAgNC4yCiMgU3RlcCA0LjIuMQpORFZJLnJlZ2lvbltpcy5uYShORFZJLnJlZ2lvbildIDwtIDAKTkRWSS5tYXQgPC0gbWF0cml4KE5EVkkucmVnaW9uQGRhdGFAdmFsdWVzLCBucm93ID0gTkRWSS5yZWdpb25AbnJvd3MsIG5jb2wgPSBORFZJLnJlZ2lvbkBuY29scywgYnlyb3cgPSBUUlVFKQojIFN0ZXAgNC4yLjIKIyBTY2FsZSB0aGUgTkRWSSB0byBbMCwxXQptMCA8LSBtaW4oTkRWSS5tYXQpCm0xIDwtIG1heChORFZJLm1hdCkKTkRWSS5tYXQxIDwtIChORFZJLm1hdCAtIG0wKSAvIChtMSAtIG0wKQoKI09wZW5JbWFnZVI6OmltYWdlU2hvdyhORFZJLm1hdDEpICAjIEZpZy4gOQpwbG90X3NsaWMgPSBPcGVuSW1hZ2VSOjpOb3JtYWxpemVPYmplY3QoTkRWSS5tYXQxKQpwbG90X3NsaWMgPSBnckRldmljZXM6OmFzLnJhc3RlcihwbG90X3NsaWMpCmdyYXBoaWNzOjpwbG90KHBsb3Rfc2xpYykKCmBgYAoKKipTdGVwIDUuMToqKiBXZSBhcmUgbm93IHJlYWR5IHRvIGNhcnJ5IG91dCB0aGUgc2VnbWVudGF0aW9uIG9mIHRoZSBORFZJIGRhdGEuIFNpbmNlIHRoZSBzdHJ1Y3R1cmUgb2YgdGhlIE5EVkkgaW1hZ2UgdG8gYmUgYW5hbHl6ZWQgaXMgdGhlIHNhbWUgYXMgdGhhdCBvZiB0aGUgZmFsc2UgY29sb3IgaW1hZ2UsIHdlIGNhbiBzaW1wbHkgY3JlYXRlIGEgY29weSBvZiB0aGlzIGltYWdlLCBmaWxsIGl0IHdpdGggdGhlIE5EVkkgZGF0YSwgYW5kIHJ1biBpdCB0aHJvdWdoIHRoZSBzdXBlcnBpeGVsIHNlZ21lbnRhdGlvbiBmdW5jdGlvbi4KCmBgYHtyfQojIFN0ZXAgNS4xCkZhbHNlLkNvbG9yIDwtIHJlYWRJbWFnZSgiRmFsc2VDb2xvci5qcGciKQpORFZJLmRhdGEgPC0gRmFsc2UuQ29sb3IKTkRWSS5kYXRhWywsMV0gPC0gTkRWSS5tYXQxCk5EVkkuZGF0YVssLDJdIDwtIE5EVkkubWF0MQpORFZJLmRhdGFbLCwzXSA8LSBORFZJLm1hdDEKCk5EVkkuODAgPSBzdXBlcnBpeGVscyhpbnB1dF9pbWFnZSA9IE5EVkkuZGF0YSwKICAgICAgICAgICAgICAgICAgICAgIG1ldGhvZCA9ICJzbGljIiwgICNtZXRob2QgPSAic2xpY28iLAogICAgICAgICAgICAgICAgICAgICAgc3VwZXJwaXhlbCA9IDM3LCAgICNzdXBlcnBpeGVsID0gMjAwLAogICAgICAgICAgICAgICAgICAgICAgY29tcGFjdG5lc3MgPSAzLCAKICAgICAgICAgICAgICAgICAgICAgIHJldHVybl9zbGljX2RhdGEgPSBUUlVFLAogICAgICAgICAgICAgICAgICAgICAgcmV0dXJuX2xhYmVscyA9IFRSVUUsIAogICAgICAgICAgICAgICAgICAgICAgd3JpdGVfc2xpYyA9ICIiLAogICAgICAgICAgICAgICAgICAgICAgdmVyYm9zZSA9IEZBTFNFKQoKT3BlbkltYWdlUjo6aW1hZ2VTaG93KE5EVkkuODAkc2xpY19kYXRhKQpwbG90X3NsaWMgPSBPcGVuSW1hZ2VSOjpOb3JtYWxpemVPYmplY3QoTkRWSS44MCRzbGljX2RhdGEpCnBsb3Rfc2xpYyA9IGdyRGV2aWNlczo6YXMucmFzdGVyKHBsb3Rfc2xpYykKZ3JhcGhpY3M6OnBsb3QocGxvdF9zbGljKQpgYGAKClRoZSBzZWdtZW50YXRpb24gcHJvY2VzcyBpcyBub3cgY2FuIGJlIG9yZ2FuaXplZCBpbnRvIHR3byBzdGVwcy4KClRoZSBmaXJzdCBzdGVwIHdpbGwgYmUgdG8gcmVwbGFjZSBlYWNoIG9mIHRoZSBzdXBlcnBpeGVscyBnZW5lcmF0ZWQgYnkgdGhlIE9wZW5JbWFnZVIgZnVuY3Rpb24gc3VwZXJwaXhlbCgpIHdpdGggb25lIGluIHdoaWNoIGVhY2ggcGl4ZWwgaGFzIHRoZSBzYW1lIHZhbHVlLCBjb3JyZXNwb25kaW5nIHRvIGEgbWVhc3VyZSBvZiBjZW50cmFsIHRlbmRlbmN5IChlLmcuIG1lYW4pIG9mIHRoZSBvcmlnaW5hbCBzdXBlcnBpeGVsLgoKKipGdW5jdGlvbjoqKiBJZGVudGlmeSBhIG1lYXN1cmUgb2YgY2VudHJhbCB0ZW5kZW5jeSBvZiBlYWNoIHN1cGVycGl4ZWwKCmBgYHtyfQojIElkZW50aWZ5IGEgbWVhc3VyZSBvZiBjZW50cmFsIHRlbmRlbmN5IG9mIGVhY2ggc3VwZXJwaXhlbAptYWtlLnNlZ21lbnRzIDwtIGZ1bmN0aW9uKHgsIGZ0bil7CiMgVGhlIGFyZ3VtZW50IGZ0biBpcyBhbnkgZnVuY3Rpb25hbCBtZWFzdXJlIG9mIGNlbnRyYWwgdGVuZGVuY3kKICAgeiA8LSB4CiMgRm9yIGVhY2ggaWRlbnRpZmllZCBzdXBlcnBpeGVsLCBjb21wdXRlIG1lYXN1cmUgb2YgY2VudHJhbCB0ZW5kZW5jeQogICBmb3IgKGsgaW4gdW5pcXVlKGFzLnZlY3Rvcih4JGxhYmVscykpKXsKIyBJZGVudGlmeSBtZW1iZXJzIG9mIHRoZSBzdXBlcnBpeGVsIGhhdmluZyB0aGUgZ2l2ZW4gbGFiZWwKICAgICAgaW4uc3VwZXIgPC0gbWF0cml4KDAsIG5yb3coeCRsYWJlbCksIG5jb2woeCRsYWJlbCkpCiAgICAgIGZvciAoaSBpbiAxOm5yb3coeCRsYWJlbCkpCiAgICAgICAgIGZvciAoaiBpbiAxOm5jb2woeCRsYWJlbCkpCiAgICAgICAgICAgIGlmICh4JGxhYmVsW2ksal0gPT0gaykKICAgICAgICAgICAgICAgaW4uc3VwZXJbaSxqXSA8LSAxCiNJZGVudGlmeSB0aGUgYm91bmRhcnkgY2VsbHMgYXMgaGF2aW5nIGFsbCB2YWx1ZXMgMAogICAgICBvbi5ib3VuZCA8LSBtYXRyaXgoMCwgbnJvdyh4JGxhYmVsKSwgbmNvbCh4JGxhYmVsKSkKICAgICAgZm9yIChpIGluIDE6bnJvdyh4JGxhYmVsKSkKICAgICAgICAgZm9yIChqIGluIDE6bmNvbCh4JGxhYmVsKSkKICAgICAgICAgICAgaWYgKGluLnN1cGVyW2ksal0gPT0gMSl7CiAgICAgICAgICAgICAgIGlmICh4JHNsaWNfZGF0YVtpLGosMV0gPT0gMCAmIHgkc2xpY19kYXRhW2ksaiwyXSA9PSAwIAogICAgICAgICAgICAgICAgICAmIHgkc2xpY19kYXRhW2ksaiwzXSA9PSAwKQogICAgICAgICAgICAgICAgICAgICBvbi5ib3VuZFtpLGpdIDwtIDEKICAgICAgICAgfQojSWRlbnRpZnkgdGhlIHN1cGVycGl4ZWwgY2VsbHMgbm90IG9uIHRoZSBib3VuZGFyeQogICAgICBzdXAuZGF0YSA8LSBtYXRyaXgoMCwgbnJvdyh4JGxhYmVsKSwgbmNvbCh4JGxhYmVsKSkKICAgICAgICAgZm9yIChpIGluIDE6bnJvdyh4JGxhYmVsKSkKICAgICAgICAgZm9yIChqIGluIDE6bmNvbCh4JGxhYmVsKSkKICAgICAgICAgICAgaWYgKGluLnN1cGVyW2ksal0gPT0gMSAmIG9uLmJvdW5kW2ksal0gPT0gMCkKICAgICAgICAgICAgICAgc3VwLmRhdGFbaSxqXSA8LSAxCiMgQ29tcHV0ZSB0aGUgbWVhc3VyZSBvZiBjZW50cmFsIHRlbmRlbmN5IG9mIHRoZSBjZWxscyBpbiBSLCBHLCBCCiAgICAgIGZvciAobiBpbiAxOjMpewojIENyZWF0ZSBhIG1hdHJpeCBNIG9mIHRoZSBzYW1lIHNpemUgYXMgdGhlIG1hdHJpeCBvZiBzdXBlcnBpeGVsIHZhbHVlcwogICAgICAgICBNIDwtIG1hdHJpeCgwLCBkaW0oeCRzbGljX2RhdGEpWzFdLCBkaW0oeCRzbGljX2RhdGEpWzJdKSAKICAgICAgICAgZm9yIChpIGluIDE6bnJvdyh4JGxhYmVsKSkKICAgICAgICAgICAgZm9yIChqIGluIDE6bmNvbCh4JGxhYmVsKSkKIyBBc3NpZ24gdG8gTSB0aGUgdmFsdWVzIGluIHRoZSBzdXBlcnBpeGVsCiAgICAgICAgICAgICAgIGlmIChzdXAuZGF0YVtpLGpdID09IDEpIE1baSxqXSA8LSB4JHNsaWNfZGF0YVtpLGosbl0KICAgICAgICAgIGlmIChsZW5ndGgoTVt3aGljaChNID4gMCAmIE0gPCAyNTUpXSkgPiAwKQojIENvbXB1dGUgdGhlIG1lYXN1cmUgb2YgY2VudHJhbCB0ZW5kZW5jeQogICAgICAgICAgICBmdG4ubiA8LSByb3VuZChmdG4oTVt3aGljaChNID4gMCAmIE0gPCAyNTUpXSksIDApCiAgICAgICAgIGVsc2UKICAgICAgICAgICAgZnRuLm4gPC0gMAogICAgICAgICBmb3IgKGkgaW4gMTpucm93KHgkbGFiZWwpKQogICAgICAgICAgICBmb3IgKGogaW4gMTpuY29sKHgkbGFiZWwpKQogICAgICAgICAgICAgICBpZiAoaW4uc3VwZXJbaSxqXSA9PSAxKSB6JHNsaWNfZGF0YVtpLGosbl0gPC0gZnRuLm4KICAgICAgICAgICB9CiAgICAgIH0KICAgcmV0dXJuKHopCiAgIH0KYGBgCgpgYGB7cn0KTkRWSS5tZWFucyA8LSAgbWFrZS5zZWdtZW50cyhORFZJLjgwLCBtZWFuKQpgYGAKClRoZSBzZWNvbmQgc3RlcCB3aWxsIGJlIHRvIHVzZSB0aGUgay1tZWFucyB1bnN1cGVydmlzZWQgY2x1c3RlcmluZyBwcm9jZWR1cmUgdG8gb3JnYW5pemUgdGhlIHN1cGVycGl4ZWxzIGZyb20gc3RlcCAxIGludG8gYSBzZXQgb2YgY2x1c3RlcnMgYW5kIGdpdmUgZWFjaCBjbHVzdGVyIGEgdmFsdWUgY29ycmVzcG9uZGluZyB0byBhIG1lYXN1cmUgb2YgY2VudHJhbCB0ZW5kZW5jeSBvZiB0aGUgY2x1c3Rlci4KClRoZSBsYW5kIGlzIHViZGl2aWRlZCBpbnRvIGZpdmUgdHlwZXM6IDEsIDIsIDMsIDQsIDUuCgpUaGUgcmFzdGVyIGZ1bmN0aW9uIHJhdGlmeSgpIGlzIHVzZWQgdG8gYXNzaWduIGRlc2NyaXB0aXZlIGZhY3RvciBsZXZlbHMgdG8gdGhlIGNsdXN0ZXJzLgoKYGBge3J9CmxpYnJhcnkocmFzdGVyVmlzKQojIExvb2sgYXQgdGhlIGluZGl2aWR1YWwgdmFsdWVzCnNvcnQodW5pcXVlKGFzLnZlY3RvcihORFZJLm1lYW5zJHNsaWNfZGF0YVssLDFdKSkpCiMgR3JvdXAgaW50byBmaXZlIGNsdXN0ZXJzCnNldC5zZWVkKDEyMykgCk5EVkkuY2x1cyA8LSBrbWVhbnMoYXMudmVjdG9yKE5EVkkubWVhbnMkc2xpY19kYXRhWywsMV0pLCA1KQp2ZWdlLmNsYXNzIDwtIG1hdHJpeChORFZJLmNsdXMkY2x1c3RlciwgbnJvdyA9IE5EVkkucmVnaW9uQG5yb3dzLAogICBuY29sID0gTkRWSS5yZWdpb25AbmNvbHMsIGJ5cm93ID0gRkFMU0UpCmltYWdlU2hvdyh2ZWdlLmNsYXNzKSAjIEp1c3QgYSBjaGVjayBub3Qgc2hvd24gYXMgYSBmaWd1cmUKcGxvdF9zbGljID0gT3BlbkltYWdlUjo6Tm9ybWFsaXplT2JqZWN0KHZlZ2UuY2xhc3MpCnBsb3Rfc2xpYyA9IGdyRGV2aWNlczo6YXMucmFzdGVyKHBsb3Rfc2xpYykKZ3JhcGhpY3M6OnBsb3QocGxvdF9zbGljKQpjbGFzcy5yYXMgPC0gcmFzdGVyKHZlZ2UuY2xhc3MpCmNsYXNzLnJhcyA8LSByYXRpZnkoY2xhc3MucmFzKQpyYXQuY2xhc3MgPC0gbGV2ZWxzKGNsYXNzLnJhcylbWzFdXQpyYXQuY2xhc3MkbGFuZGNvdmVyIDwtIGMoIjEiLCAiMiIsICIzIiwgIjQiLCAiNSIpCmxldmVscyhjbGFzcy5yYXMpIDwtIHJhdC5jbGFzcwpsZXZlbHBsb3QoY2xhc3MucmFzLCBtYXJnaW49RkFMU0UsIGNvbC5yZWdpb25zPSBjKCJsaWdodGdyZWVuIiwgImJsYWNrIiwKICAidGFuIiwgImRhcmtncmVlbiIsICJiZWlnZSIpLCBtYWluID0gIkxhbmQgQ292ZXIgVHlwZXMiKSAjIEZpZy4gMTkKcGxvdChjbGFzcy5yYXMsIGNvbCA9IGMoImxpZ2h0Z3JlZW4iLCAiYmxhY2siLAogICJ0YW4iLCAiZGFya2dyZWVuIiwgImJlaWdlIiksIG1haW4gPSAiTGFuZCBDb3ZlciBUeXBlcyIsCiAgIGxlZ2VuZCA9IEZBTFNFKSAjIEZpZy4gMTkKI2xlZ2VuZCgicmlnaHQiLCBsZWdlbmQgPSBjKCIxIiwgIjIiLCAiMyIsICI0IiwKIyAgIjUiKSwgZmlsbCA9IGMoImRhcmtncmVlbiIsICJ0YW4iLCAibGlnaHRncmVlbiIsICJncmVlbiIsCiMgICJibGFjayIpKQojcGxvdChORFZJLnBvbHltbnMsIGFkZCA9IFRSVUUpIApgYGAK